UVa/11451 - Water restrictions/11451.cpp

   1 #include <iostream>
   2 #include <vector>
   3
   4 using namespace std;
   5
   6 int pos[10], m[10], C, best, S;
   7
   8 void backtrack(vector<int> &n){
   9   for (int i=0, sum = 0; i<S; ++i){
  10     sum += n[i];
  11     if (sum > C) return;
  12   }
  13
  14   int mask = 0;
  15   for (int i=0; i<S; ++i){
  16     if (n[i] > 0){
  17       for (int j=pos[i]-n[i]; j<= pos[i]+n[i]; ++j){
  18         mask = mask | (1<<j);
  19       }
  20     }
  21   }
  22
  23   best >?= __builtin_popcount(mask);
  24
  25   for (int i=0; i<S; ++i){
  26     if (n[i]+1 <= m[i]){
  27       n[i]++;
  28       backtrack(n);
  29       n[i]--;
  30     }
  31   }
  32 }
  33
  34 int main(){
  35   int T;
  36   cin >> T;
  37   while (T--){
  38     int L;
  39     cin >> L >> S;
  40     for (int i=0; i<S; ++i){
  41       cin >> pos[i];
  42     }
  43     cin >> C;
  44     for (int i=0; i<S; ++i){
  45       cin >> m[i];
  46     }
  47
  48     best = -1;
  49     vector<int> n(S, 0);
  50     backtrack(n);
  51     cout << best << endl;
  52
  53   }
  54   return 0;
  55 }